package offer;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

@FunctionalInterface
public interface NonBinaryTreePreorder {
    List<Integer> preorder(Node root);
}
/*
迭代
class NonBinaryTreePreorderImpl2 implements NonBinaryTreePreorder{
    @Override

    public List<Integer> preorder(Node root) {
        if(root == null){
            return new ArrayList<>();
        }else{
            List<Integer> ans = new ArrayList<>();
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()){
                Node top = stack.pop();
                ans.add(top.val);
                List<Node> childs = top.children;
                int n = childs.size();
                for (int i = n - 1; i >= 0; i--) {
                    stack.push(childs.get(i));
                }
            }
            return ans;
        }

}

 */
/*
递归
class NonBinaryTreePreorderImpl1 implements NonBinaryTreePreorder{

    @Override
    public List<Integer> preorder(Node root) {
        if(root == null){
            return new ArrayList<>();
        }else{
            List<Integer> ans = new ArrayList<>();
            dfs(ans, root);
            return ans;
        }
    }
    private void dfs(List<Integer> ans, Node root){
        List<Node> childs = root.children;
        ans.add(root.val);
        for(Node children : childs){
            dfs(ans, children);
        }
    }
}

 */

/*
    树的定义
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

 */